package 第六周;

/*
 * @author  YxinMiracle
 * @date  2022-05-05 18:57
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 最长公共子序列 {

    // 动态规划
    public int longestCommonSubsequence(String text1, String text2) {

        int m = text1.length();
        int n = text2.length();

        int[][] nums = new int[m + 1][n + 1];

        text1 = " " + text1;
        text2 = " " + text2;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i) == text2.charAt(j)){
                    nums[i][j] = nums[i-1][j-1] + 1;
                }else {
                    nums[i][j] = Math.max(nums[i-1][j],nums[i][j-1]);
                }
            }
        }
        return nums[m][n];

    }

}
